/* 
 * File:   graph.h
 * Author: aishwarya
 *
 * Created on March 12, 2011, 11:08 AM
 * This represents a Graph using an adjacency list.
 * The dynamic array adj[] represents nvertices [0...nvertices-1] of the graph.
 * Each element adj[u] contains a list of vertices v adjacent to u i.e., (u,v)
 * is a edge in G.
 */

#ifndef GRAPH_H
#define	GRAPH_H

#include "avdtech.h"

#ifdef	__cplusplus
extern "C" {
#endif

    enum {
        undirected = 0, directed = 1
    };

    typedef int weight;

    typedef struct _edge {
        int v; /* adjacent node */
        weight w; /* cost of edge (u,v) */
        struct _edge *next; /* pointer to next edge */
    } EDGE;

    typedef struct _edge_pair {
        int u, v; /* connected vertices */
        weight w; /* cost of edge (u,v) */        
    } EDGE_PAIR;

    typedef struct _graph {
        EDGE **adj; /* adjacency list of vertex u */
        int nvertices; /* number of vertices in the graph */
        int nedges; /* number of edge in the graph */
        short is_directed; /* directed or undirected */
        int *degree; /* degree of each vertex */
        size_t sizeof_edge; /* sizeof EDGE */
    } GRAPH;
    
    void graph_init(GRAPH *g, int nvertices, int nedges, short is_directed);
    void add_edge(GRAPH *g, int u, int v, weight cost);
    void graph_display(GRAPH *g);
    void graph_clean(GRAPH *g);
    int graph_create_edge_pairs(GRAPH *g, EDGE_PAIR *e);


#ifdef	__cplusplus
}
#endif

#endif	/* GRAPH_H */

